import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class MinMutation {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>();
        Set<String> geneSet = new HashSet<>();
        char[] geneCharacter = {'A', 'C', 'G', 'T'};
        for (String s : bank) {
            bankSet.add(s);
        }
        if (startGene.equals(endGene)) {
            return 0;
        }
        if (!bankSet.contains(endGene)) {
            return -1;
        }
        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        geneSet.add(startGene);
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            while (size-- > 0) {
                String tmp = queue.poll();
                for (int i = 0; i < 8; i++) {
                    char[] cc = tmp.toCharArray();
                    for (int j = 0; j < 4; j++) {
                        cc[i] = geneCharacter[j];
                        String change = new String(cc);
                        if (!geneSet.contains(change) && bankSet.contains(change)) {
                            if (change.equals(endGene)) {
                                return step;
                            }
                            geneSet.add(change);
                            queue.add(change);
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        MinMutation minMutation = new MinMutation();
        System.out.println(minMutation.minMutation("AACCGGTT", "AACCGGTA", new String[]{"AACCGGTA"}));
    }
}
